4050 // File system implementation.  Four layers:
4051 //   + Blocks: allocator for raw disk blocks.
4052 //   + Files: inode allocator, reading, writing, metadata.
4053 //   + Directories: inode with special contents (list of other inodes!)
4054 //   + Names: paths like /usr/rtm/xv6/fs.c for convenient naming.
4055 //
4056 // Disk layout is: superblock, inodes, block in-use bitmap, data blocks.
4057 //
4058 // This file contains the low-level file system manipulation
4059 // routines.  The (higher-level) system call implementations
4060 // are in sysfile.c.
4061 
4062 #include "types.h"
4063 #include "defs.h"
4064 #include "param.h"
4065 #include "stat.h"
4066 #include "mmu.h"
4067 #include "proc.h"
4068 #include "spinlock.h"
4069 #include "buf.h"
4070 #include "fs.h"
4071 #include "file.h"
4072 
4073 #define min(a, b) ((a) < (b) ? (a) : (b))
4074 static void itrunc(struct inode*);
4075 
4076 // Read the super block.
4077 static void
4078 readsb(int dev, struct superblock *sb)
4079 {
4080   struct buf *bp;
4081 
4082   bp = bread(dev, 1);
4083   memmove(sb, bp->data, sizeof(*sb));
4084   brelse(bp);
4085 }
4086 
4087 // Zero a block.
4088 static void
4089 bzero(int dev, int bno)
4090 {
4091   struct buf *bp;
4092 
4093   bp = bread(dev, bno);
4094   memset(bp->data, 0, BSIZE);
4095   bwrite(bp);
4096   brelse(bp);
4097 }
4098 
4099 
4100 // Blocks.
4101 
4102 // Allocate a disk block.
4103 static uint
4104 balloc(uint dev)
4105 {
4106   int b, bi, m;
4107   struct buf *bp;
4108   struct superblock sb;
4109 
4110   bp = 0;
4111   readsb(dev, &sb);
4112   for(b = 0; b < sb.size; b += BPB){
4113     bp = bread(dev, BBLOCK(b, sb.ninodes));
4114     for(bi = 0; bi < BPB; bi++){
4115       m = 1 << (bi % 8);
4116       if((bp->data[bi/8] & m) == 0){  // Is block free?
4117         bp->data[bi/8] |= m;  // Mark block in use on disk.
4118         bwrite(bp);
4119         brelse(bp);
4120         return b + bi;
4121       }
4122     }
4123     brelse(bp);
4124   }
4125   panic("balloc: out of blocks");
4126 }
4127 
4128 // Free a disk block.
4129 static void
4130 bfree(int dev, uint b)
4131 {
4132   struct buf *bp;
4133   struct superblock sb;
4134   int bi, m;
4135 
4136   bzero(dev, b);
4137 
4138   readsb(dev, &sb);
4139   bp = bread(dev, BBLOCK(b, sb.ninodes));
4140   bi = b % BPB;
4141   m = 1 << (bi % 8);
4142   if((bp->data[bi/8] & m) == 0)
4143     panic("freeing free block");
4144   bp->data[bi/8] &= ~m;  // Mark block free on disk.
4145   bwrite(bp);
4146   brelse(bp);
4147 }
4148 
4149 
4150 // Inodes.
4151 //
4152 // An inode is a single, unnamed file in the file system.
4153 // The inode disk structure holds metadata (the type, device numbers,
4154 // and data size) along with a list of blocks where the associated
4155 // data can be found.
4156 //
4157 // The inodes are laid out sequentially on disk immediately after
4158 // the superblock.  The kernel keeps a cache of the in-use
4159 // on-disk structures to provide a place for synchronizing access
4160 // to inodes shared between multiple processes.
4161 //
4162 // ip->ref counts the number of pointer references to this cached
4163 // inode; references are typically kept in struct file and in proc->cwd.
4164 // When ip->ref falls to zero, the inode is no longer cached.
4165 // It is an error to use an inode without holding a reference to it.
4166 //
4167 // Processes are only allowed to read and write inode
4168 // metadata and contents when holding the inode's lock,
4169 // represented by the I_BUSY flag in the in-memory copy.
4170 // Because inode locks are held during disk accesses,
4171 // they are implemented using a flag rather than with
4172 // spin locks.  Callers are responsible for locking
4173 // inodes before passing them to routines in this file; leaving
4174 // this responsibility with the caller makes it possible for them
4175 // to create arbitrarily-sized atomic operations.
4176 //
4177 // To give maximum control over locking to the callers,
4178 // the routines in this file that return inode pointers
4179 // return pointers to *unlocked* inodes.  It is the callers'
4180 // responsibility to lock them before using them.  A non-zero
4181 // ip->ref keeps these unlocked inodes in the cache.
4182 
4183 struct {
4184   struct spinlock lock;
4185   struct inode inode[NINODE];
4186 } icache;
4187 
4188 void
4189 iinit(void)
4190 {
4191   initlock(&icache.lock, "icache");
4192 }
4193 
4194 
4195 
4196 
4197 
4198 
4199 
4200 static struct inode* iget(uint dev, uint inum);
4201 
4202 // Allocate a new inode with the given type on device dev.
4203 struct inode*
4204 ialloc(uint dev, short type)
4205 {
4206   int inum;
4207   struct buf *bp;
4208   struct dinode *dip;
4209   struct superblock sb;
4210 
4211   readsb(dev, &sb);
4212   for(inum = 1; inum < sb.ninodes; inum++){  // loop over inode blocks
4213     bp = bread(dev, IBLOCK(inum));
4214     dip = (struct dinode*)bp->data + inum%IPB;
4215     if(dip->type == 0){  // a free inode
4216       memset(dip, 0, sizeof(*dip));
4217       dip->type = type;
4218       bwrite(bp);   // mark it allocated on the disk
4219       brelse(bp);
4220       return iget(dev, inum);
4221     }
4222     brelse(bp);
4223   }
4224   panic("ialloc: no inodes");
4225 }
4226 
4227 // Copy inode, which has changed, from memory to disk.
4228 void
4229 iupdate(struct inode *ip)
4230 {
4231   struct buf *bp;
4232   struct dinode *dip;
4233 
4234   bp = bread(ip->dev, IBLOCK(ip->inum));
4235   dip = (struct dinode*)bp->data + ip->inum%IPB;
4236   dip->type = ip->type;
4237   dip->major = ip->major;
4238   dip->minor = ip->minor;
4239   dip->nlink = ip->nlink;
4240   dip->size = ip->size;
4241   memmove(dip->addrs, ip->addrs, sizeof(ip->addrs));
4242   bwrite(bp);
4243   brelse(bp);
4244 }
4245 
4246 
4247 
4248 
4249 
4250 // Find the inode with number inum on device dev
4251 // and return the in-memory copy.
4252 static struct inode*
4253 iget(uint dev, uint inum)
4254 {
4255   struct inode *ip, *empty;
4256 
4257   acquire(&icache.lock);
4258 
4259   // Try for cached inode.
4260   empty = 0;
4261   for(ip = &icache.inode[0]; ip < &icache.inode[NINODE]; ip++){
4262     if(ip->ref > 0 && ip->dev == dev && ip->inum == inum){
4263       ip->ref++;
4264       release(&icache.lock);
4265       return ip;
4266     }
4267     if(empty == 0 && ip->ref == 0)    // Remember empty slot.
4268       empty = ip;
4269   }
4270 
4271   // Allocate fresh inode.
4272   if(empty == 0)
4273     panic("iget: no inodes");
4274 
4275   ip = empty;
4276   ip->dev = dev;
4277   ip->inum = inum;
4278   ip->ref = 1;
4279   ip->flags = 0;
4280   release(&icache.lock);
4281 
4282   return ip;
4283 }
4284 
4285 // Increment reference count for ip.
4286 // Returns ip to enable ip = idup(ip1) idiom.
4287 struct inode*
4288 idup(struct inode *ip)
4289 {
4290   acquire(&icache.lock);
4291   ip->ref++;
4292   release(&icache.lock);
4293   return ip;
4294 }
4295 
4296 
4297 
4298 
4299 
4300 // Lock the given inode.
4301 void
4302 ilock(struct inode *ip)
4303 {
4304   struct buf *bp;
4305   struct dinode *dip;
4306 
4307   if(ip == 0 || ip->ref < 1)
4308     panic("ilock");
4309 
4310   acquire(&icache.lock);
4311   while(ip->flags & I_BUSY)
4312     sleep(ip, &icache.lock);
4313   ip->flags |= I_BUSY;
4314   release(&icache.lock);
4315 
4316   if(!(ip->flags & I_VALID)){
4317     bp = bread(ip->dev, IBLOCK(ip->inum));
4318     dip = (struct dinode*)bp->data + ip->inum%IPB;
4319     ip->type = dip->type;
4320     ip->major = dip->major;
4321     ip->minor = dip->minor;
4322     ip->nlink = dip->nlink;
4323     ip->size = dip->size;
4324     memmove(ip->addrs, dip->addrs, sizeof(ip->addrs));
4325     brelse(bp);
4326     ip->flags |= I_VALID;
4327     if(ip->type == 0)
4328       panic("ilock: no type");
4329   }
4330 }
4331 
4332 // Unlock the given inode.
4333 void
4334 iunlock(struct inode *ip)
4335 {
4336   if(ip == 0 || !(ip->flags & I_BUSY) || ip->ref < 1)
4337     panic("iunlock");
4338 
4339   acquire(&icache.lock);
4340   ip->flags &= ~I_BUSY;
4341   wakeup(ip);
4342   release(&icache.lock);
4343 }
4344 
4345 
4346 
4347 
4348 
4349 
4350 // Caller holds reference to unlocked ip.  Drop reference.
4351 void
4352 iput(struct inode *ip)
4353 {
4354   acquire(&icache.lock);
4355   if(ip->ref == 1 && (ip->flags & I_VALID) && ip->nlink == 0){
4356     // inode is no longer used: truncate and free inode.
4357     if(ip->flags & I_BUSY)
4358       panic("iput busy");
4359     ip->flags |= I_BUSY;
4360     release(&icache.lock);
4361     itrunc(ip);
4362     ip->type = 0;
4363     iupdate(ip);
4364     acquire(&icache.lock);
4365     ip->flags = 0;
4366     wakeup(ip);
4367   }
4368   ip->ref--;
4369   release(&icache.lock);
4370 }
4371 
4372 // Common idiom: unlock, then put.
4373 void
4374 iunlockput(struct inode *ip)
4375 {
4376   iunlock(ip);
4377   iput(ip);
4378 }
4379 
4380 // Inode contents
4381 //
4382 // The contents (data) associated with each inode is stored
4383 // in a sequence of blocks on the disk.  The first NDIRECT blocks
4384 // are listed in ip->addrs[].  The next NINDIRECT blocks are
4385 // listed in the block ip->addrs[NDIRECT].
4386 
4387 // Return the disk block address of the nth block in inode ip.
4388 // If there is no such block, bmap allocates one.
4389 static uint
4390 bmap(struct inode *ip, uint bn)
4391 {
4392   uint addr, *a;
4393   struct buf *bp;
4394 
4395   if(bn < NDIRECT){
4396     if((addr = ip->addrs[bn]) == 0)
4397       ip->addrs[bn] = addr = balloc(ip->dev);
4398     return addr;
4399   }
4400   bn -= NDIRECT;
4401 
4402   if(bn < NINDIRECT){
4403     // Load indirect block, allocating if necessary.
4404     if((addr = ip->addrs[NDIRECT]) == 0)
4405       ip->addrs[NDIRECT] = addr = balloc(ip->dev);
4406     bp = bread(ip->dev, addr);
4407     a = (uint*)bp->data;
4408     if((addr = a[bn]) == 0){
4409       a[bn] = addr = balloc(ip->dev);
4410       bwrite(bp);
4411     }
4412     brelse(bp);
4413     return addr;
4414   }
4415 
4416   panic("bmap: out of range");
4417 }
4418 
4419 // Truncate inode (discard contents).
4420 // Only called after the last dirent referring
4421 // to this inode has been erased on disk.
4422 static void
4423 itrunc(struct inode *ip)
4424 {
4425   int i, j;
4426   struct buf *bp;
4427   uint *a;
4428 
4429   for(i = 0; i < NDIRECT; i++){
4430     if(ip->addrs[i]){
4431       bfree(ip->dev, ip->addrs[i]);
4432       ip->addrs[i] = 0;
4433     }
4434   }
4435 
4436   if(ip->addrs[NDIRECT]){
4437     bp = bread(ip->dev, ip->addrs[NDIRECT]);
4438     a = (uint*)bp->data;
4439     for(j = 0; j < NINDIRECT; j++){
4440       if(a[j])
4441         bfree(ip->dev, a[j]);
4442     }
4443     brelse(bp);
4444     bfree(ip->dev, ip->addrs[NDIRECT]);
4445     ip->addrs[NDIRECT] = 0;
4446   }
4447 
4448 
4449 
4450   ip->size = 0;
4451   iupdate(ip);
4452 }
4453 
4454 // Copy stat information from inode.
4455 void
4456 stati(struct inode *ip, struct stat *st)
4457 {
4458   st->dev = ip->dev;
4459   st->ino = ip->inum;
4460   st->type = ip->type;
4461   st->nlink = ip->nlink;
4462   st->size = ip->size;
4463 }
4464 
4465 // Read data from inode.
4466 int
4467 readi(struct inode *ip, char *dst, uint off, uint n)
4468 {
4469   uint tot, m;
4470   struct buf *bp;
4471 
4472   if(ip->type == T_DEV){
4473     if(ip->major < 0 || ip->major >= NDEV || !devsw[ip->major].read)
4474       return -1;
4475     return devsw[ip->major].read(ip, dst, n);
4476   }
4477 
4478   if(off > ip->size || off + n < off)
4479     return -1;
4480   if(off + n > ip->size)
4481     n = ip->size - off;
4482 
4483   for(tot=0; tot<n; tot+=m, off+=m, dst+=m){
4484     bp = bread(ip->dev, bmap(ip, off/BSIZE));
4485     m = min(n - tot, BSIZE - off%BSIZE);
4486     memmove(dst, bp->data + off%BSIZE, m);
4487     brelse(bp);
4488   }
4489   return n;
4490 }
4491 
4492 
4493 
4494 
4495 
4496 
4497 
4498 
4499 
4500 // Write data to inode.
4501 int
4502 writei(struct inode *ip, char *src, uint off, uint n)
4503 {
4504   uint tot, m;
4505   struct buf *bp;
4506 
4507   if(ip->type == T_DEV){
4508     if(ip->major < 0 || ip->major >= NDEV || !devsw[ip->major].write)
4509       return -1;
4510     return devsw[ip->major].write(ip, src, n);
4511   }
4512 
4513   if(off > ip->size || off + n < off)
4514     return -1;
4515   if(off + n > MAXFILE*BSIZE)
4516     n = MAXFILE*BSIZE - off;
4517 
4518   for(tot=0; tot<n; tot+=m, off+=m, src+=m){
4519     bp = bread(ip->dev, bmap(ip, off/BSIZE));
4520     m = min(n - tot, BSIZE - off%BSIZE);
4521     memmove(bp->data + off%BSIZE, src, m);
4522     bwrite(bp);
4523     brelse(bp);
4524   }
4525 
4526   if(n > 0 && off > ip->size){
4527     ip->size = off;
4528     iupdate(ip);
4529   }
4530   return n;
4531 }
4532 
4533 // Directories
4534 
4535 int
4536 namecmp(const char *s, const char *t)
4537 {
4538   return strncmp(s, t, DIRSIZ);
4539 }
4540 
4541 
4542 
4543 
4544 
4545 
4546 
4547 
4548 
4549 
4550 // Look for a directory entry in a directory.
4551 // If found, set *poff to byte offset of entry.
4552 // Caller must have already locked dp.
4553 struct inode*
4554 dirlookup(struct inode *dp, char *name, uint *poff)
4555 {
4556   uint off, inum;
4557   struct buf *bp;
4558   struct dirent *de;
4559 
4560   if(dp->type != T_DIR)
4561     panic("dirlookup not DIR");
4562 
4563   for(off = 0; off < dp->size; off += BSIZE){
4564     bp = bread(dp->dev, bmap(dp, off / BSIZE));
4565     for(de = (struct dirent*)bp->data;
4566         de < (struct dirent*)(bp->data + BSIZE);
4567         de++){
4568       if(de->inum == 0)
4569         continue;
4570       if(namecmp(name, de->name) == 0){
4571         // entry matches path element
4572         if(poff)
4573           *poff = off + (uchar*)de - bp->data;
4574         inum = de->inum;
4575         brelse(bp);
4576         return iget(dp->dev, inum);
4577       }
4578     }
4579     brelse(bp);
4580   }
4581   return 0;
4582 }
4583 
4584 // Write a new directory entry (name, inum) into the directory dp.
4585 int
4586 dirlink(struct inode *dp, char *name, uint inum)
4587 {
4588   int off;
4589   struct dirent de;
4590   struct inode *ip;
4591 
4592   // Check that name is not present.
4593   if((ip = dirlookup(dp, name, 0)) != 0){
4594     iput(ip);
4595     return -1;
4596   }
4597 
4598 
4599 
4600   // Look for an empty dirent.
4601   for(off = 0; off < dp->size; off += sizeof(de)){
4602     if(readi(dp, (char*)&de, off, sizeof(de)) != sizeof(de))
4603       panic("dirlink read");
4604     if(de.inum == 0)
4605       break;
4606   }
4607 
4608   strncpy(de.name, name, DIRSIZ);
4609   de.inum = inum;
4610   if(writei(dp, (char*)&de, off, sizeof(de)) != sizeof(de))
4611     panic("dirlink");
4612 
4613   return 0;
4614 }
4615 
4616 // Paths
4617 
4618 // Copy the next path element from path into name.
4619 // Return a pointer to the element following the copied one.
4620 // The returned path has no leading slashes,
4621 // so the caller can check *path=='\0' to see if the name is the last one.
4622 // If no name to remove, return 0.
4623 //
4624 // Examples:
4625 //   skipelem("a/bb/c", name) = "bb/c", setting name = "a"
4626 //   skipelem("///a//bb", name) = "bb", setting name = "a"
4627 //   skipelem("a", name) = "", setting name = "a"
4628 //   skipelem("", name) = skipelem("////", name) = 0
4629 //
4630 static char*
4631 skipelem(char *path, char *name)
4632 {
4633   char *s;
4634   int len;
4635 
4636   while(*path == '/')
4637     path++;
4638   if(*path == 0)
4639     return 0;
4640   s = path;
4641   while(*path != '/' && *path != 0)
4642     path++;
4643   len = path - s;
4644   if(len >= DIRSIZ)
4645     memmove(name, s, DIRSIZ);
4646   else {
4647     memmove(name, s, len);
4648     name[len] = 0;
4649   }
4650   while(*path == '/')
4651     path++;
4652   return path;
4653 }
4654 
4655 // Look up and return the inode for a path name.
4656 // If parent != 0, return the inode for the parent and copy the final
4657 // path element into name, which must have room for DIRSIZ bytes.
4658 static struct inode*
4659 namex(char *path, int nameiparent, char *name)
4660 {
4661   struct inode *ip, *next;
4662 
4663   if(*path == '/')
4664     ip = iget(ROOTDEV, ROOTINO);
4665   else
4666     ip = idup(proc->cwd);
4667 
4668   while((path = skipelem(path, name)) != 0){
4669     ilock(ip);
4670     if(ip->type != T_DIR){
4671       iunlockput(ip);
4672       return 0;
4673     }
4674     if(nameiparent && *path == '\0'){
4675       // Stop one level early.
4676       iunlock(ip);
4677       return ip;
4678     }
4679     if((next = dirlookup(ip, name, 0)) == 0){
4680       iunlockput(ip);
4681       return 0;
4682     }
4683     iunlockput(ip);
4684     ip = next;
4685   }
4686   if(nameiparent){
4687     iput(ip);
4688     return 0;
4689   }
4690   return ip;
4691 }
4692 
4693 struct inode*
4694 namei(char *path)
4695 {
4696   char name[DIRSIZ];
4697   return namex(path, 0, name);
4698 }
4699 
4700 struct inode*
4701 nameiparent(char *path, char *name)
4702 {
4703   return namex(path, 1, name);
4704 }
4705 
4706 
4707 
4708 
4709 
4710 
4711 
4712 
4713 
4714 
4715 
4716 
4717 
4718 
4719 
4720 
4721 
4722 
4723 
4724 
4725 
4726 
4727 
4728 
4729 
4730 
4731 
4732 
4733 
4734 
4735 
4736 
4737 
4738 
4739 
4740 
4741 
4742 
4743 
4744 
4745 
4746 
4747 
4748 
4749 
